package main.xht;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.*;

public class CriticalEquationSolverBigDecimal {

    // 设定精度（保留小数位数）
    private static final int PRECISION = 10;
    private static final int SCALE_FACTOR = (int) Math.pow(10, PRECISION);

    public static void main(String[] args) {
        // 示例输入：方程系数和目标值
        BigDecimal[] coefficients = {
                BigDecimal.valueOf(1).divide(BigDecimal.valueOf(20), PRECISION, RoundingMode.HALF_UP),
                BigDecimal.valueOf(3).divide(BigDecimal.valueOf(20), PRECISION, RoundingMode.HALF_UP),
                BigDecimal.valueOf(10).divide(BigDecimal.valueOf(20), PRECISION, RoundingMode.HALF_UP)
        };

        BigDecimal[] coefficients1 = {
                BigDecimal.ONE, BigDecimal.ONE, BigDecimal.ONE
        };

        BigDecimal a = BigDecimal.valueOf(1.0);  // 目标值

        solveCriticalSolutions(coefficients, coefficients1, a);
    }

    public static void solveCriticalSolutions(BigDecimal[] n, BigDecimal[] n1, BigDecimal a) {
        int k = n.length;
        if (n.length != n1.length) {
            System.out.println("错误：系数数组长度不一致");
            return;
        }

        // 1. 输入验证和转换
        List<BigIntegerTuple> scaledTuples = new ArrayList<>();
        BigInteger scaledA = BigInteger.ZERO;
        BigInteger minSum = BigInteger.ZERO;

        try {
            scaledA = a.multiply(new BigDecimal(SCALE_FACTOR))
                    .setScale(0, RoundingMode.HALF_UP)
                    .toBigIntegerExact();

            for (int i = 0; i < k; i++) {
                if (n[i].compareTo(BigDecimal.ZERO) <= 0) {
                    System.out.println("错误：所有系数必须大于0");
                    return;
                }

                // 转换为整数表示（高精度）
                BigInteger scaledValue = n[i].multiply(new BigDecimal(SCALE_FACTOR))
                        .setScale(0, RoundingMode.HALF_UP)
                        .toBigIntegerExact();

                BigInteger minValue = n1[i].multiply(new BigDecimal(SCALE_FACTOR))
                        .setScale(0, RoundingMode.HALF_UP)
                        .toBigIntegerExact();

                scaledTuples.add(new BigIntegerTuple(scaledValue, minValue));
                minSum = minSum.add(minValue);
            }
        } catch (ArithmeticException e) {
            System.out.println("精度溢出错误：数值过大或精度过高");
            return;
        }

        // 转换后的目标值
        BigInteger A_prime = scaledA.subtract(minSum);

        if (A_prime.compareTo(BigInteger.ZERO) < 0) {
            System.out.println("无解：变量取最小值时已超过目标值");
            return;
        }

        // 2. 动态规划表初始化
        Map<BigInteger, List<int[]>> dp = new HashMap<>();
        dp.put(BigInteger.ZERO, Collections.singletonList(new int[k])); // 初始解：所有 xi' = 0

        // 3. 动态规划填表
        for (int i = 0; i < k; i++) {
            BigInteger Ni = scaledTuples.get(i).scaledValue;
            Map<BigInteger, List<int[]>> newDp = new HashMap<>();

            for (Map.Entry<BigInteger, List<int[]>> entry : dp.entrySet()) {
                BigInteger currentSum = entry.getKey();
                List<int[]> combs = entry.getValue();

                for (int[] comb : combs) {
                    // 计算当前系数最多可增加的次数
                    BigInteger remainder = A_prime.subtract(currentSum);
                    int maxM = remainder.compareTo(BigInteger.ZERO) > 0 && Ni.compareTo(BigInteger.ZERO) > 0 ?
                            remainder.divide(Ni).intValueExact() : 0;

                    for (int m = 0; m <= maxM; m++) {
                        BigInteger newSum = currentSum.add(Ni.multiply(BigInteger.valueOf(m)));
                        int[] newComb = Arrays.copyOf(comb, k);
                        newComb[i] += m;

                        newDp.computeIfAbsent(newSum, key -> new ArrayList<>()).add(newComb);
                    }
                }
            }
            dp = newDp;
        }

        // 4. 收集所有目标解
        List<int[]> solutions = dp.getOrDefault(A_prime, Collections.emptyList());

        // 5. 过滤临界解
        List<int[]> criticalSolutions = new ArrayList<>();
        for (int[] comb : solutions) {
            if (isCriticalSolution(comb, scaledTuples, A_prime)) {
                criticalSolutions.add(comb);
            }
        }

        // 6. 结果输出
        if (criticalSolutions.isEmpty()) {
            System.out.println("无满足临界条件的解");
        } else {
            System.out.println("临界解（共 " + criticalSolutions.size() + " 种）：");
            for (int[] comb : criticalSolutions) {
                printSolution(comb, scaledTuples, n1);
            }
        }
    }

    // 检查是否为临界解
    private static boolean isCriticalSolution(int[] comb, List<BigIntegerTuple> scaledTuples, BigInteger target) {
        for (int i = 0; i < comb.length; i++) {
            BigInteger tempSum = BigInteger.ZERO;

            for (int j = 0; j < comb.length; j++) {
                BigInteger multiplier = BigInteger.valueOf(comb[j] + (i == j ? 1 : 0));
                tempSum = tempSum.add(scaledTuples.get(j).scaledValue.multiply(multiplier));
            }

            if (tempSum.compareTo(target) == 0) {
                return false;
            }
        }
        return true;
    }

    // 打印解决方案
    private static void printSolution(int[] comb, List<BigIntegerTuple> scaledTuples, BigDecimal[] minValues) {
        List<BigDecimal> solutionValues = new ArrayList<>();
        boolean allAboveMin = true;

        // 计算实际变量值
        for (int i = 0; i < comb.length; i++) {
            BigDecimal value = new BigDecimal(comb[i] + 1)
                    .add(minValues[i].divide(new BigDecimal(SCALE_FACTOR), PRECISION, RoundingMode.HALF_UP));
            solutionValues.add(value);

            if (value.compareTo(minValues[i]) < 0) {
                allAboveMin = false;
            }
        }

        if (allAboveMin) {
            System.out.print("x = [");
            for (int i = 0; i < solutionValues.size(); i++) {
                System.out.print(solutionValues.get(i).setScale(PRECISION, RoundingMode.HALF_UP).stripTrailingZeros());
                if (i < solutionValues.size() - 1) {
                    System.out.print(", ");
                }
            }
            System.out.println("]");
        }
    }

    // 辅助类：存储缩放后的值和最小值
    private static class BigIntegerTuple {
        final BigInteger scaledValue;
        final BigInteger minValue;

        BigIntegerTuple(BigInteger scaledValue, BigInteger minValue) {
            this.scaledValue = scaledValue;
            this.minValue = minValue;
        }
    }

}
